package org.getOffer.offer42;

import java.util.Arrays;

/**
 * @Author yu
 * @Date 2021/10/15
 */
public class Solution {
    public static void main(String[] args) {

        int[] ints = {-2,1,-3,4,-1,2,1,-5,4};

        //int[] ints = {1,2,-1,-2,2,1,-2,1,4,-5,4};

        //int[] ints = {-1, -2};

        //int[] ints = {-2, 1};

        Solution solution = new Solution();
        System.out.println(solution.maxSubArray(ints));

    }

    public int maxSubArray(int[] nums) {

//        int left = 0, right = 0;
//
//        int max = 0, sum = 0;
//
//        for (int i = 0; i< nums.length; i++) {
//            sum += nums[right++];
//
//            if (sum <= 0) {
//                sum -= nums[left];
//                left++;
//            }
//            max = Math.max(sum, max);
//        }
//
//        return max;

//        int left = 0, right = 1;
//
//        int max = nums[0], sum = nums[0];
//
//        for (int i = 0; i< nums.length-1; i++) {
//            sum += nums[right++];
//
//            if (sum <= 0 || nums[left] <= 0) {
//                sum -= nums[left++];
//            }
//            max = Math.max(sum, max);
//        }
//
//        return max;

        int right = 1;

        int max = nums[0], sum = nums[0];

        for (int i = 0; i< nums.length-1; i++) {
            if (sum <= 0  && right < nums.length) {
                sum = 0;
            }
            sum += nums[right++];

            max = Math.max(sum, max);

        }

        return max;

    }
}
